A paradox for expected hitting times

Abstract

We prove a counterintuitive result concerning the expected hitting/absorption time for a class of Markov chains. The “paradox” already shows itself in the following elementary example that is suitable for undergraduate teaching: Batman and the Joker perform independent discrete-time random walks on the vertices of a square until they meet, starting from opposite vertices. Batman always moves (and clockwise and anticlockwise steps are equally likely), while the Joker remains still on any given step with probability q∈[0,1]. On average the Joker survives for twice as long by staying still with arbitrarily small but positive probability (in the limit as limq↓0) than by always moving (when q = 0..